package lanQiaoBei.数学知识.快速幂;
import java.io.*;
import java.util.*;
/*快速幂  https://blog.csdn.net/qq_62417282/article/details/128752235(详解)
* 给定 n 组 ai,bi,pi，对于每组数据，求出 ai ^ bi mod pi 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含三个整数 ai,bi,pi。

输出格式

对于每组数据，输出一个结果，表示 ai ^ bi mod pi  的值。

每个结果占一行。

数据范围

1≤n≤100000,
1≤ai,bi,pi≤2×1e9

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1
* */
public class P1 {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    final static int N=100010;

    static void scan()throws Exception{

    }
    static int qmi(int a,int k,int m){
           int res=1;
           while(k>0){
                if((k&1)==1)res=res*a%m;
                k=k>>1;
                a=a*a%m;
           }
           return res;
    }
    public static void main(String[]args)throws Exception{
           int n=Integer.parseInt(br.readLine());
           while(n-->0){
                String[]ss=br.readLine().split(" ");
                int a=Integer.parseInt(ss[0]),k=Integer.parseInt(ss[1]),m=Integer.parseInt(ss[2]);
                System.out.println(qmi(a,k,m));
           }
    }
}
